Scheduling jobs to run on a single machine is a fundamental optimization problem, as is scheduling jobs to run on unrelated machines. Typically in such scheduling problems the jobs arrive “online” and over time. In order to complete a job, the job needs to be assigned a certain amount of processing, referred to as its processing volume.
Traditionally, devices given a set of jobs were run at their fastest possible speed, with the goal being to minimize the average flow time, where the flow time of a job (sometimes referred as the response time) is the duration of time between its release and completion. A standard objective is minimizing (a weighted) sum of flow times.
However, the amount of energy consumed by the processor or processors has become an important consideration, because of the high energy cost (e.g., of a datacenter), along with the wear on components, (and possibly the battery life on mobile devices). A machine can run at many different speeds, with the tradeoff that higher speeds process jobs faster but consume more energy. The power (the rate of energy consumed) by a processor is a given function of the speed, e.g., the cube of the speed. Thus, if there is time to complete a job at a slower speed, running at the fastest speed is not desirable.
Scheduling jobs in a way that saves energy yet complete the jobs in a desired time is a question of knowing which job to schedule next, (which may change as more important jobs arrive), and at what speed to run the machine. This is a complex problem that heretofore did not have a good solution or solutions.